package class10;

import java.util.HashMap;
import java.util.Map;

/**
 * 设计RandomPool结构
 * 题目：
 * 设计一种结构，在该结构中有三个功能：
 * insert(key)、delete(key)、getRandom()
 * <p>
 * 思路：
 * map1(str->index)   map2(index->str)
 * "A"  0                0   "A"
 * "B"  1                1   "A"
 * "C"  2                2   "A"
 * "D"  3                3   "A"
 * <p>
 * 注意删除：
 * 1.当删除key时，需要先获取key，然后获取index
 * 2.获取最后一个index，然后插入到移除被移除的key的位置
 */
public class Code02_RandomPool {
    public static void main(String[] args) {
        Pool<String> pool = new Pool<>();
        pool.insert("A");
        pool.insert("B");
        pool.insert("C");
        pool.insert("D");

        System.out.println(pool.getRandom());
        pool.delete("B");
        System.out.println(pool.getRandom());

    }

    static class Pool<K> {
        private Map<K, Integer> keyIndexMap;
        private Map<Integer, K> indexKeyMap;
        private int size;

        public Pool() {
            this.indexKeyMap = new HashMap<>();
            this.keyIndexMap = new HashMap<>();
            this.size = 0;
        }

        public void insert(K key) {
            if (!keyIndexMap.containsKey(key)) {
                this.keyIndexMap.put(key, this.size);
                this.indexKeyMap.put(this.size, key);
                size++;
            }
        }

        public K getRandom() {
            if (size == 0) return null;
            int index = (int) (Math.random() * this.size); // 0 ~ size -1
            return this.indexKeyMap.get(index);
        }

        public void delete(K key) {
            if (keyIndexMap.containsKey(key)) {
                Integer index = keyIndexMap.get(key);
                Integer lastIndex = --size;
                K lastKey = indexKeyMap.get(lastIndex);
                keyIndexMap.put(key, index);
                indexKeyMap.put(index, lastKey);
                keyIndexMap.remove(key);
                indexKeyMap.remove(lastIndex);
            }
        }
    }
}
